class RabinKarp
  def RabinKarp.match(source, pattern)
    return false if source.size < pattern.size
    
    pattern_hash = first_hash(pattern)
    seq_hash = first_hash(source[0, pattern.size])
    
    for i in 0..(source.size - pattern.size) do
      if i > 0 then
        next_byte = source[i + pattern.size - 1]
        discarded_byte = source[i - 1]
        seq_hash = roll_hash(next_byte, discarded_byte, seq_hash, pattern.size)
      end
      
      collision = (seq_hash == pattern_hash)
      
      if collision then
        byte_matching = source[i, pattern.size] == pattern
        return i if byte_matching
      end
    end
    
    nil
  end
  
  ##############################################################################
  # HASH PART
  # 
  # Important note: in Ruby we don't have automatic overflow like Java, so we
  # end up with huge hash values, which COULD be unefficient.
  # In real Ruby implementations (!) this should be probably taken into account.
  ##############################################################################

  HASH_CONST = 101 # Wikipedia's ;-)

  def RabinKarp.first_hash(seq)
    # it's quite surprising that there isn't a method to convert from a string
    # to an array of chars; so that we can't iterate every char of a string along
    # with its position

    # sorry for the unreadability, but this is quite funny
    (0...seq.size).inject(0) {|hash, i| hash + seq[i].to_i * HASH_CONST ** (seq.size - i - 1)}
  end

  def RabinKarp.roll_hash(next_byte, discarded_byte, old_hash, pattern_len)
    old_hash -= discarded_byte * HASH_CONST ** (pattern_len - 1)
    old_hash *= HASH_CONST
    old_hash += next_byte # * HASH_CONST ** 0
  end
end